#include<stdio.h>
const int maxn=100010;
int g(long long b,long long p,long long mod)
{
	int ans=1;
	while(p){
		if(p&1){
			ans=ans*b%mod;
		}
		b=b*b%mod;
		p>>=1;
	}
	return ans;
}
int main()
{
	int n,a[maxn];
	long long b,p,mod;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%lld%lld%lld",&b,&p,&mod);
		a[i]=g(b,p,mod);
	}
	for(int i=0;i<n;i++){
		printf("%d\n",a[i]);
	}
	return 0;
}
